package cn.edu.xjtu.carlWay.stackAndQueue.slidingWindowMaximum;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 239. 滑动窗口最大值
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * <p>
 * 返回 滑动窗口中的最大值 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] ints = maxSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 超时了，有个测试用例10w个数据！！！离谱
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(
                new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o2 - o1;
                    }
                }
        );
        int index = 0;
        int[] ret = new int[nums.length - k + 1];

        int right = 0;
        for (; right < k; right++) {
            queue.offer(nums[right]);
        }
        ret[index++] = queue.peek();
        for (; right < nums.length; right++) {
            queue.remove(nums[right - k]);
            queue.offer(nums[right]);
            ret[index++] = queue.peek();
        }

        return ret;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int maxVal = Integer.MIN_VALUE;
        int[] slideArr = new int[k];
        int[] ret = new int[nums.length - k + 1];
        int retIndex = 0;
        int slideIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                maxVal = Math.max(maxVal, nums[i]);
                slideArr[i] = nums[i];
            } else {
                ret[retIndex++] = maxVal;
                int temp = slideArr[slideIndex];
                slideArr[slideIndex] = nums[i];

                if (temp == maxVal) {
                    maxVal = getMax(slideArr);
                }
                if (nums[i] > maxVal) {
                    maxVal = nums[i];
                }
                slideIndex = (slideIndex + 1) % slideArr.length;

            }
        }
        ret[retIndex] = maxVal;
        return ret;
    }

    public static int getMax(int[] array) {
        int maxVal = Integer.MIN_VALUE;
        for (int i : array) {
            maxVal = Math.max(maxVal, i);
        }
        return maxVal;
    }
}

